using System;
using System.Collections.Generic;
using System.Text;

namespace Mono.Graph.PriorityQueue
{
    public class MyHeap<T> : IRangeIndexedPriorityQueue<T>
    {
        public MyHeap(){}
        public MyHeap(int size) { ((IRangeIndexedPriorityQueue<T>)this).Create(size); }
        T[] Val;
        int size;
        int[] up;
        int[] left;
        int[] right;
        int[] down;
        bool[] exist;
        int first;
        IComparer<T> Cmp;
        void linkLeft(int ne, int old) {
            int ll = left[old];
            right[ll] = ne;
            right[ne] = old;
            left[old] = ne;
            left[ne] = ll;

        }
        void linkDown(int d, int u)
        {
            if (down[u] > -1)
            {
                linkLeft(d, down[u]);
            }
            else
            {
                left[d] = right[d] = down[u] = d;
                up[d] = u;
            }
        }
        void unlinkUp(int a)
        {
            if (up[a] > -1)
            {
                if (right[a] == a) down[up[a]] = -1;
                else
                {
                    down[up[a]] = right[a];
                    up[right[a]] = up[a];
                }
                up[a] = -1;
            }

        }
        void unlink(int a)
        {
            if (right[a] > -1) left[right[a]] = left[a];
            if (left[a] > -1) right[left[a]] = right[a];
        }
        void consolidate ()
        {
            if(first==-1)return;
            right[left[first]] = -1;
            left[first] = -1;
            while (right[first] != -1)
            {
                int akt = first;
                int r=right[akt];
                while (r > -1)
                {
                    int rr = right[r];
                    if (Cmp.Compare(Val[akt],Val[r]) < 0)
                    {
                        unlink(r);
                        linkDown(r, akt);
                    }
                    else
                    {
                        if (akt == first) first = r;
                        unlink(akt);
                        linkDown(akt, r);
                    }
                    akt = rr;
                    if (akt < 0) break;
                    r = right[akt];
                }
            }
            left[first] = right[first] = first;
        }

        


        #region IPriorityQueue<T> Members

        int IRangeIndexedPriorityQueue<T>.Size
        {
            get { return size; }
        }

        T IRangeIndexedPriorityQueue<T>.TopVal
        {
            get {
                consolidate();
                return Val[first];
            }
        }

        int IRangeIndexedPriorityQueue<T>.TopKey
        {
            get {
                consolidate();
                return first;
            }
        }

        void IRangeIndexedPriorityQueue<T>.Create(int SizeoOfHeap, IComparer<T> cmp)
        {
            Cmp = cmp;
            size = 0;
            first = -1;
            Val = new T[SizeoOfHeap];
            right = new int[SizeoOfHeap];
            down = new int[SizeoOfHeap];
            up = new int[SizeoOfHeap];
            left = new int[SizeoOfHeap];
            exist = new bool[SizeoOfHeap];
        }

        void IRangeIndexedPriorityQueue<T>.Create(int SizeOfHeap)
        {
            ((IRangeIndexedPriorityQueue<T>)this).Create(SizeOfHeap, Comparer<T>.Default);
        }

        void IRangeIndexedPriorityQueue<T>.Insert(int Key, T Value)
        {
            Val[Key] = Value;
            up[Key] = down[Key] = -1;
            if (first > -1)
            {
                linkLeft(Key, first);
            }
            else {
                first = left[Key] = right[Key] = Key;
            }
            exist[Key] = true;
            size++;

        }

        void IRangeIndexedPriorityQueue<T>.DecreaseKey(int Key, T NewValue)
        {
            if (!exist[Key]) return;
            if (Cmp.Compare(Val[Key],NewValue) > 0) {
                Val[Key] = NewValue;
                if (Key == first) return;
                int d = down[Key];
                if (d > -1)
                {
                    if (up[Key]>-1 && right[Key] == Key)// !!!
                    {
                        up[d] = up[Key];
                        down[up[Key]] = d;
                        up[Key] = -1;
                    }
                    else
                    {
                        right[left[Key]] = right[d];
                        left[right[Key]] = d;
                        left[right[d]] = left[Key];
                        right[d] = right[Key];
                        if (up[Key] > -1)
                        {
                            up[d] = up[Key];
                            down[up[Key]] = d;
                            up[Key] = -1;
                        }
                        else {
                            up[d] = -1;
                        }
                    }

                }
                else 
                {
                    unlinkUp(Key);
                    unlink(Key);
                }
                //
                down[Key] = -1;
                linkLeft(Key, first);
            }
        }

        void IRangeIndexedPriorityQueue<T>.Pop()
        {
            consolidate();
            exist[first] = false;
            first = down[first];
            size--;
            if (size>0) up[first] = -1;
        }


        T IRangeIndexedPriorityQueue<T>.GetVal(int indx)
        {
            if (exist[indx]) return Val[indx];
            throw new IndexOutOfRangeException("there is no index :" + indx + " on heap");
        }

        void IRangeIndexedPriorityQueue<T>.SetVal(int indx, T value)
        {
            if (exist[indx]) ((IRangeIndexedPriorityQueue<T>)this).DecreaseKey(indx, value);
            else ((IRangeIndexedPriorityQueue<T>)this).Insert(indx, value);
        }

        #endregion
        /*
#region Debug
		#if DEBUG
        void valLinks(int akt, ref StringBuilder err)
        {
            if(akt==first)if (up[akt] != -1) err.AppendLine("first is a child");
            if (left[akt] > -1)
            {
                if (right[left[akt]] != akt || !inserted[left[akt]]) err.AppendLine("Bad Left link akt=" + akt + " left=" + left[akt]);
            }
            if (right[akt] > -1)
            {
                if (left[right[akt]] != akt || !inserted[right[akt]]) err.AppendLine("Bad Left link akt=" + akt + " right=" + right[akt]);
            }
            if (up[akt] > -1)
            {
                if (down[up[akt]] != akt || !inserted[up[akt]]) err.AppendLine("Bad up link akt=" + akt + " up=" + up[akt]);
            }
            if (down[akt] > -1)
            {
                if (up[down[akt]] != akt || !inserted[down[akt]]) err.AppendLine("Bad down link akt=" + akt + " down=" + down[akt]);
            }
        }
        int val(int akt, ref StringBuilder err)
        {
            if (akt < 0) return 0;
            int ret = 0;
            valLinks(akt,ref err);
            //if (down[up[akt]] != akt) err.AppendLine("bad child :" + akt);
            for (int i = right[akt]; i != akt; i = right[i])
            {
                if (i < 0) throw new Exception("ll");
                ret += val(down[i],ref err) + 1;
                valLinks(i, ref err);
            }
            ret += val(down[akt], ref err);
            return ret + 1;

        }
        public string IS_VALID
        {
            get
            {
                StringBuilder ret = new StringBuilder();
                //for (int i = 1; i < size; i++)
                
                    int tmp=val(first,ref ret);
                    if(size != tmp)ret.AppendLine("size="+size+" returned="+tmp);
                    //if (Val[heap[i]].CompareTo(Val[heap[((i + 1) / 2 - 1)]]) < 0) ret.AppendLine("" + i);
                
                if (ret.Length == 0) ret.AppendLine("YES");
                return ret.ToString();
            }
        }
#endif 
	#endregion*/

    }
}
